HW#1 --- last modified February 07 2019 04:29:27..

Solution set.

Due date: Feb 12

Files to be submitted:
  Hw1.zip

Purpose:To get familiar with: comparing run-times of algorithms, loop-invariants and proofs of correctness, designing and analyzing algorithms using divide and conquer.

The main course outcomes covered by this assignment are:

LO4 -- Use advanced sorting techniques (radix sort, heapsort, mergesort, quicksort).

LO6 -- Solve recurrence relations representing the running time of an algorithm designed using a divide-and-conquer strategy.

LO8 -- Comprehend algorithms designed using greedy, divide-and-conquer, and dynamic programming techniques.

Specification:

For this homework there will be two parts: a written part and a coding part. Both of these should be submitted in your Hw1.zip file. For the written part I want you to do the following problems below, and put your solutions into a file Hw1.pdf (no Word docs please!) which you put in your zip file.

1. For each function `f(n)` and time `t` in the following table, determine the largest size `n` of a problem that can be solved in time `t`, assuming that the algorithm to solve the problem takes `f(n)` microseconds.

   	1 seconds	1 minute	1 hour	1 day	1 month	1 year	1 century
   `log log n`
   `2 log n`
   `n`
   `n^2log n`
   `n^{5/2}`
   `3^n`

2. Illustrate the operation of the Insertion-Sort algorithm from book on the array `A=langle 5, 4, 3, 2, 1 rangle` and `A=langle 42, 13, 54, 19, 21 rangle`.
3. Use mathematical induction to show that when `n` is an exact power of `4`, the solution of the recurrence relation `T(n)={(8,if n=4),(4 T(n/4) + 2n,if n=4^k text{, for }k > 1):}`
   is `T(n) = n log_2 n.`
4. Problem 2.3 out of the book (make sure this is in your own words and you don't look on the internet!).

A good solution to each of the problems above would involve, first writing down the problem then directly answering the question asked. Proofs by induction should have clearly stated base case and induction steps arguments, as well as conclusions. Use complete sentences in any arguments you make.

For the coding part of Hw1, I want you to code a variation on merge sort, which we will call 3-way merge sort. On sequences of size 0, 3-way merge sort returns the empty sequence. On sequences of size 1, 3-way merge sort just returns that sequence. On a sequence of length two, it compares the two elements and returns them from least to greatest. On sequences of length `n`, it splits the sequence into three sequences of size `lfloor n/3 rfloor`, `lfloor n/3 rfloor`, and the remainder of the elements respectively. For example, on the sequence `langle 3, 1, 8, 5, 7 rangle` it would split it into `langle 3 rangle`, `langle 1 rangle`, `langle 8,5, 7 rangle`. On `langle 10, 13, 21, 68, 52, 27 rangle` it would split it into `langle 10, 13 rangle`, `langle 21, 68 rangle`, `langle 52, 27 rangle`. It then executes 3-way merge sort on each of the sub-sequences and merges their results together to produce the final sorted output.

You will code this algorithm in a file Hw1.java which should conform to the Departmental coding guidelines for Java. Include this file (but no class files or jars) in the Hw1.zip file you submit. It will be compiled from the command-line with the command:

javac Hw1.java

Your program will be tested from the command line by passing the sequence as command line arguments:

java Hw1 elt_1 elt_2 elt_3 ...

For example,

java Hw1 10 13 21 68 52 27

If the sequence is fewer than three elements your program should write "Input", echo the input, and just say "Sorted:" and give the sorted output. For example:

java Hw1 21 19
Input:21 19
Sorted:19 21

On three or more elements, it echos "Input:" and lists the inputs, "Subsequences:" lists each of these on separate lines. Then it recurses to sort each of these in turn (this might echo things to the output). Finally, it writes "Sorted:" and the sorted output. For example:

java Hw1 10 13 21 68 52 27
Input:10 13 21 68 52 27
Subsequences:
10 13
21 68
52 27
Input:10 13
Sorted:10 13
Input:21 68
Sorted:21 68
Input:52 27
Sorted:27 52
Sorted:10 13 21 27 52 68

If you would like to compare what your code does versus what I think it should output, you can use my compiled Python version of three-way mergesort.

This completes the description of Hw1.java

Point Breakdown